//
//  735. 小行星碰撞.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/9.
//

import Foundation

//https://leetcode.cn/problems/asteroid-collision/
//给定一个整数数组 asteroids，表示在同一行的小行星。
//
//对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
//
//找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。
//
// 
//
//示例 1：
//
//输入：asteroids = [5,10,-5]
//输出：[5,10]
//解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
//示例 2：
//
//输入：asteroids = [8,-8]
//输出：[]
//解释：8 和 -8 碰撞后，两者都发生爆炸。
//示例 3：
//
//输入：asteroids = [10,2,-5]
//输出：[10]
//解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
// 
//
//提示：
//
//2 <= asteroids.length <= 104
//-1000 <= asteroids[i] <= 1000
//asteroids[i] != 0

func 小行星碰撞(_ asteroids: [Int]) -> [Int] {
//    var res = [Int]()
//
//    for i in 0..<asteroids.count {
//
//        if asteroids[i] > 0 {
//          //! 右边移动,则先保存数据
//          res.append(asteroids[i])
//        } else {
//          //! 当前行星向左移动，需要进行对撞测试
//          //! 判断当前行星是否需要保存
//          var flag = true
//
//          //! 因为向左移动，所以需要去数组中查找行星，是否会相撞
//          while !res.isEmpty {
//
//            let last = res.popLast()!
//            if last < 0 {
//              //! 说明方向一致，不会相撞,将弹出的行星重新入栈
//              res.append(last)
//              break
//            } else {
//              //! 会相撞，此时需要比对行星大小
//              let size = -asteroids[i]
//              if last > size {
//                //! 当前行星太小，被毁灭，
//                res.append(last)
//                flag = false
//                break
//              } else if last == size {
//                //! 同归于尽，被毁灭
//                flag = false
//                break
//              } else {
//                //! 当前行星继续左行
//              }
//            }
//          }
//
//          //! 说明当前行星依然存在，添加入队
//          if flag == true {
//            res.append(asteroids[i])
//          }
//        }
//    }
//
//    return res
    
    var stack: [Int] = []
    for item in asteroids {
        var shouldContinue = false
        while stack.last != nil, stack.last! > 0, item < 0 {
            if stack.last! == -item {
                stack.removeLast()
                shouldContinue = true
                break
            } else if stack.last! < -item {
                stack.removeLast()
            } else {
                shouldContinue = true
                break
            }
        }
        if !shouldContinue {
            stack.append(item)
        }
    }
    return stack
}
